翻訳と辞書 Words near each other ・ Orders, decorations, and medals of Serbia ・ Orders, decorations, and medals of SFR Yugoslavia ・ Orders, decorations, and medals of Slovakia ・ Orders, decorations, and medals of Slovenia ・ Orders, decorations, and medals of South Korea ・ Orders, decorations, and medals of South Vietnam ・ Orders, decorations, and medals of Spain ・ Orders, decorations, and medals of Swaziland ・ OrderAhead ・ Ordered Bell number ・ Ordered dithering ・ Ordered exponential ・ Ordered field ・ Ordered from the Catalogue ・ Ordered geometry ・ Ordered graph ・ Ordered list ・ Ordered logit ・ Ordered pair ・ Ordered probit ・ Ordered ring ・ Ordered semigroup ・ Ordered set operators ・ Ordered subset expectation maximization ・ Ordered to Die ・ Ordered vector space ・ Ordered weighted averaging aggregation operator ・ Orderic Vitalis ・ Orderliness ・ Orderly Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Ordered graph ： ウィキペディア英語版 Ordered graph An ordered graph is a graph with a total order over its nodes. In an ordered graph, the parents of a node are the nodes that are joined to it and precede it in the ordering. More precisely, $n$ is a parent of $m$ in the ordered graph if $(n,m)\; \backslash in\; E$ and . The width of a node is the number of its parents, and the width of an ordered graph is the maximal width of its nodes. The induced graph of an ordered graph is obtained by adding some edges to an ordering graph, using the method outlined below. The induced width of an ordered graph is the width of its induced graph. Given an ordered graph, its induced graph is another ordered graph obtained by joining some pairs of nodes that are both parents of another node. In particular, nodes are considered in turn according to the ordering, from last to first. For each node, if two of its parents are not joined by an edge, that edge is added. In other words, when considering node $n$, if both $m$ and $l$ are parents of it and are not joined by an edge, the edge $(m,l)$ is added to the graph. Since the parents of a node are always connected with each other, the induced graph is always chordal. As an example, the induced graph of an ordered graph is calculated. The ordering is represented by the position of its nodes in the figures: a is the last node and d is the first. Node $a$ is considered first. Its parents are $b$ and $c$, as they are both joined to $a$ and both precede $a$ in the ordering. Since they are not joined by an edge, one is added. Node $b$ is considered second. While this node only has $d$ as a parent in the original graph, it also has $c$ as a parent in the partially built induced graph. Indeed, $c$ is joined to $b$ and also precede $b$ in the ordering. As a result, an edge joining $c$ and $d$ is added. Considering $d$ does not produce any change, as this node has no parents. Processing nodes in order matters, as the introduced edges may create new parents, which are then relevant to the introduction of new edges. The following example shows that a different ordering produces a different induced graph of the same original graph. The ordering is the same as above but $b$ and $c$ are swapped. As in the previous case, both $b$ and $c$ are parents of $a$. Therefore, an edge between them is added. According to the new order, the second node that is considered is $c$. This node has only one parent ($b$). Therefore, no new edge is added. The third considered node is $b$. Its only parent is $d$. Indeed, $b$ and $c$ are not joined this time. As a result, no new edge is introduced. Since $d$ has no parent as well, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering. ==See also== *Directed graph *Local consistency 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ordered graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.